/*
 * @lc app=leetcode.cn id=120 lang=golang
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
// 自底向上：除了最后一层，每一层的每个节点存储与之相关联的下一层的两个路径的最小值的和
// 依次往上累加，到0，0位置就是最小路径和
func minimumTotal(triangle [][]int) int {
	for i := len(triangle) - 2; i >= 0; i-- {
		for j := 0; j < len(triangle[i]); j++ {
			triangle[i][j] += getMin(triangle[i+1][j], triangle[i+1][j+1])
		}
	}
	return triangle[0][0]
}

// 自顶向下：第一层不变，每一层的每个节点存储与之相关联的上一层的两个路径的最小值的和
// 依次往后累加，到计算最后一层时，维护最后一层的最小值即可
func minimumTotal1(triangle [][]int) int {
	length := len(triangle)
	if length == 1 {
		return triangle[0][0]
	}
	//temp:=0
	min := 1000000000
	for i := 1; i <= length-1; i++ {
		for j := 0; j < len(triangle[i]); j++ {
			if j == 0 {
				// 左边界，与之相关的路径只有一条
				triangle[i][j] += triangle[i-1][j]
			} else if j == len(triangle[i])-1 {
				// 右边界，与之相关的路径只有一条
				triangle[i][j] += triangle[i-1][j-1]
			} else {
				// 记录与之相关的路径的最小值的和
				triangle[i][j] += getMin(triangle[i-1][j-1], triangle[i-1][j])
			}
			// 计算到最后一层，维护最后一层的最小值
			if i == length-1 {
				min = getMin(min, triangle[i][j])
			}
		}
	}
	return min
}
func getMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// @lc code=end

